{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Valid Matrix Given Row and Column Sums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: restoreMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给定行和列的和求可行矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个非负整数数组&nbsp;<code>rowSum</code> 和&nbsp;<code>colSum</code>&nbsp;，其中&nbsp;<code>rowSum[i]</code>&nbsp;是二维矩阵中第 <code>i</code>&nbsp;行元素的和， <code>colSum[j]</code>&nbsp;是第 <code>j</code>&nbsp;列元素的和。换言之你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。</p>\n",
    "\n",
    "<p>请找到大小为&nbsp;<code>rowSum.length x colSum.length</code>&nbsp;的任意 <strong>非负整数</strong>&nbsp;矩阵，且该矩阵满足&nbsp;<code>rowSum</code> 和&nbsp;<code>colSum</code>&nbsp;的要求。</p>\n",
    "\n",
    "<p>请你返回任意一个满足题目要求的二维矩阵，题目保证存在 <strong>至少一个</strong>&nbsp;可行矩阵。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rowSum = [3,8], colSum = [4,7]\n",
    "<strong>输出：</strong>[[3,0],\n",
    "      [1,7]]\n",
    "<strong>解释：</strong>\n",
    "第 0 行：3 + 0 = 3 == rowSum[0]\n",
    "第 1 行：1 + 7 = 8 == rowSum[1]\n",
    "第 0 列：3 + 1 = 4 == colSum[0]\n",
    "第 1 列：0 + 7 = 7 == colSum[1]\n",
    "行和列的和都满足题目要求，且所有矩阵元素都是非负的。\n",
    "另一个可行的矩阵为：[[1,2],\n",
    "                  [3,5]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rowSum = [5,7,10], colSum = [8,6,8]\n",
    "<strong>输出：</strong>[[0,5,0],\n",
    "      [6,1,0],\n",
    "      [2,0,8]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rowSum = [14,9], colSum = [6,9,8]\n",
    "<strong>输出：</strong>[[0,9,5],\n",
    "      [6,0,3]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rowSum = [1,0], colSum = [1]\n",
    "<strong>输出：</strong>[[1],\n",
    "      [0]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rowSum = [0], colSum = [0]\n",
    "<strong>输出：</strong>[[0]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= rowSum.length, colSum.length &lt;= 500</code></li>\n",
    "\t<li><code>0 &lt;= rowSum[i], colSum[i] &lt;= 10<sup>8</sup></code></li>\n",
    "\t<li><code>sum(rowSum) == sum(colSum)</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-valid-matrix-given-row-and-column-sums](https://leetcode.cn/problems/find-valid-matrix-given-row-and-column-sums/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-valid-matrix-given-row-and-column-sums](https://leetcode.cn/problems/find-valid-matrix-given-row-and-column-sums/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,8]\\n[4,7]', '[5,7,10]\\n[8,6,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        i = j = 0  # 从左上角出发\n",
    "        while i < m and j < n:\n",
    "            rs, cs = rowSum[i], colSum[j]\n",
    "            if rs < cs:\n",
    "                mat[i][j] = rs  # 去掉第 i 行\n",
    "                colSum[j] -= rs\n",
    "                i += 1  # 往下走\n",
    "            else:\n",
    "                mat[i][j] = cs  # 去掉第 j 列\n",
    "                rowSum[i] -= cs\n",
    "                j += 1  # 往右走\n",
    "        return mat\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        i = j = 0  # 从左上角出发\n",
    "        while i < m and j < n:\n",
    "            rs, cs = rowSum[i], colSum[j]\n",
    "            if rs < cs:\n",
    "                mat[i][j] = rs  # 去掉第 i 行\n",
    "                colSum[j] -= rs\n",
    "                i += 1  # 往下走\n",
    "            else:\n",
    "                mat[i][j] = cs  # 去掉第 j 列\n",
    "                rowSum[i] -= cs\n",
    "                j += 1  # 往右走\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        x, y = len(rowSum), len(colSum)\n",
    "\n",
    "        ans = [[0] * y for _ in range(x)]\n",
    "\n",
    "        for i in range(x):\n",
    "            for j in range(y):\n",
    "                now = min(rowSum[i], colSum[j])\n",
    "                ans[i][j] = now\n",
    "                rowSum[i] -= now\n",
    "                colSum[j] -= now\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        n, m = len(rowSum), len(colSum)\n",
    "        matrix = [[0] * m for _ in range(n)]\n",
    "        i = j = 0\n",
    "        while i < n and j < m:\n",
    "            v = min(rowSum[i], colSum[j])\n",
    "            matrix[i][j] = v\n",
    "            rowSum[i] -= v\n",
    "            colSum[j] -= v\n",
    "            if rowSum[i] == 0:\n",
    "                i += 1\n",
    "            if colSum[j] == 0:\n",
    "                j += 1\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        n, m = len(rowSum), len(colSum)\n",
    "        matrix = [[0] * m for _ in range(n)]\n",
    "        i = j = 0\n",
    "        while i < n and j < m:\n",
    "            v = min(rowSum[i], colSum[j])\n",
    "            matrix[i][j] = v\n",
    "            rowSum[i] -= v\n",
    "            colSum[j] -= v\n",
    "            if rowSum[i] == 0:\n",
    "                i += 1\n",
    "            if colSum[j] == 0:\n",
    "                j += 1\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m, n = len(rowSum) , len(colSum)\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        for i, rs in enumerate(rowSum):\n",
    "            for j, cs in enumerate(colSum):\n",
    "                mat[i][j] = x = min(rs, cs)\n",
    "                rs -= x\n",
    "                colSum[j] -= x\n",
    "\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        n, m = len(rowSum), len(colSum)\n",
    "        matrix = [[0] * m for _ in range(n)]\n",
    "        i = j = 0\n",
    "        while i < n and j < m:\n",
    "            v = min(rowSum[i], colSum[j])\n",
    "            matrix[i][j] = v\n",
    "            rowSum[i] -= v\n",
    "            colSum[j] -= v\n",
    "            if rowSum[i] == 0:\n",
    "                i += 1\n",
    "            if colSum[j] == 0:\n",
    "                j += 1\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m = len(rowSum)\n",
    "        n = len(colSum)\n",
    "        rs = [[0] * n for _ in range(m)]\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < m and j < n:\n",
    "            rs[i][j] = min(rowSum[i], colSum[j])\n",
    "            rowSum[i] -= rs[i][j]\n",
    "            colSum[j] -= rs[i][j]\n",
    "\n",
    "            if rowSum[i] == 0:\n",
    "                i += 1\n",
    "            if colSum[j] == 0:\n",
    "                j += 1\n",
    "\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        # m, n = len(rowSum) , len(colSum)\n",
    "        # mat = [[0] * n for _ in range(m)]\n",
    "        # for i, rs in enumerate(rowSum):\n",
    "        #     for j, cs in enumerate(colSum):\n",
    "        #         mat[i][j] = x = min(rs, cs)\n",
    "        #         rs -= x\n",
    "        #         colSum[j] -= x\n",
    "\n",
    "        # return mat\n",
    "\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        i = j = 0 # 从左上角出发\n",
    "        while i < m and j < n:\n",
    "            rs, cs = rowSum[i], colSum[j]\n",
    "            if rs < cs:\n",
    "                mat[i][j] = rs # 去掉第i行\n",
    "                colSum[j] -= rs\n",
    "                i += 1 # 往下走\n",
    "            else:\n",
    "                mat[i][j] = cs # 去掉第j列\n",
    "                rowSum[i] -= cs\n",
    "                j += 1 # 往右走\n",
    "        return mat "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        matrix = [[0] * n for _ in range(m)]\n",
    "\n",
    "        i, j = 0, 0\n",
    "        while i < m and j < n:\n",
    "            if rowSum[i] <= colSum[j]:\n",
    "                matrix[i][j] = rowSum[i]\n",
    "                colSum[j] -= matrix[i][j]\n",
    "                i += 1\n",
    "            else:\n",
    "                matrix[i][j] = colSum[j]\n",
    "                rowSum[i] -= matrix[i][j]\n",
    "                j += 1\n",
    "        \n",
    "        return matrix\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        matrix = [[0] * n for _ in range(m)]\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i < m and j < n:\n",
    "            if rowSum[i] >= colSum[j]:\n",
    "                matrix[i][j] = colSum[j]\n",
    "                rowSum[i] -= matrix[i][j]\n",
    "                j += 1\n",
    "            else:\n",
    "                matrix[i][j] = rowSum[i]\n",
    "                colSum[j] -= matrix[i][j]\n",
    "                i += 1\n",
    "        \n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        \n",
    "        m = len(rowSum)\n",
    "        n = len(colSum)\n",
    "\n",
    "        matrix = [[0] * n for _ in range(m)]\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < m and j < n:\n",
    "            v = min(rowSum[i], colSum[j])\n",
    "            matrix[i][j] = v\n",
    "            rowSum[i] -= v\n",
    "            colSum[j] -= v\n",
    "            if rowSum[i] == 0:\n",
    "                i += 1\n",
    "            if colSum[j] == 0:\n",
    "                j += 1\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        n, m = len(rowSum), len(colSum)\n",
    "        g = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                # g[i][j] = min(rowSum[i], colSum[j])\n",
    "                if rowSum[i] < colSum[j]:\n",
    "                    g[i][j] = rowSum[i]\n",
    "                else:\n",
    "                    g[i][j] = colSum[j]\n",
    "                rowSum[i] -= g[i][j]\n",
    "                colSum[j] -= g[i][j]\n",
    "        return g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        i = j = 0  # 从左上角出发\n",
    "        while i < m and j < n:\n",
    "            rs, cs = rowSum[i], colSum[j]\n",
    "            if rs < cs:\n",
    "                mat[i][j] = rs  # 去掉第 i 行\n",
    "                colSum[j] -= rs\n",
    "                i += 1  # 往下走\n",
    "            else:\n",
    "                mat[i][j] = cs  # 去掉第 j 列\n",
    "                rowSum[i] -= cs\n",
    "                j += 1  # 往右走\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[i][j] = min(rowSum[i], colSum[j])\n",
    "                rowSum[i] -= res[i][j]\n",
    "                colSum[j] -= res[i][j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m=len(rowSum)\n",
    "        n=len(colSum)\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                now=min(rowSum[i],colSum[j])\n",
    "                dp[i][j]=now\n",
    "                rowSum[i]-=now\n",
    "                colSum[j]-=now\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m,n=len(rowSum),len(colSum)\n",
    "        ans=[[0]*n for i in range(m)]\n",
    "        colSumtemp=[0]*n\n",
    "        \n",
    "        for i in range(m):\n",
    "            left=rowSum[i]\n",
    "            index=0\n",
    "            while left:\n",
    "                ans[i][index]=min(left,colSum[index]-colSumtemp[index])\n",
    "                left-=ans[i][index]\n",
    "                colSumtemp[index]+=ans[i][index]\n",
    "                index+=1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        # 贪心\n",
    "        r = len(rowSum)\n",
    "        c = len(colSum)\n",
    "        matrix = [[0]*c for _ in range(r)]\n",
    "\n",
    "        for i, rs in enumerate(rowSum):\n",
    "            for j, cs in enumerate(colSum):\n",
    "                x = min(rs, cs)\n",
    "                matrix[i][j] = x \n",
    "                rs -= x \n",
    "                colSum[j] -= x\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        res = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                val = min(rowSum[i], colSum[j])\n",
    "                res[i][j] = val\n",
    "                rowSum[i] -= val\n",
    "                colSum[j] -= val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        n, m = len(rowSum), len(colSum)\n",
    "        matrix = [[0] * m for _ in range(n)]\n",
    "        i = j = 0\n",
    "        while i < n and j < m:\n",
    "            v = min(rowSum[i], colSum[j])\n",
    "            matrix[i][j] = v\n",
    "            rowSum[i] -= v\n",
    "            colSum[j] -= v\n",
    "            if rowSum[i] == 0:\n",
    "                i += 1\n",
    "            if colSum[j] == 0:\n",
    "                j += 1\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m,n=len(rowSum),len(colSum)\n",
    "        mat = [[0]*n for _ in range(m)]\n",
    "        for i,rs in enumerate(rowSum):\n",
    "            for j,cs in enumerate(colSum):\n",
    "                mat[i][j] = x = min(rs,cs)\n",
    "                rs -= x\n",
    "                colSum[j]-=x\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        # 一行一行的填\n",
    "        # rs代表行和\n",
    "        # cs代表列和\n",
    "        ans = [[0]*len(colSum) for _ in range(len(rowSum))]\n",
    "        for i,rs in enumerate(rowSum):\n",
    "            for j,cs in enumerate(colSum):\n",
    "                ans[i][j] = x = min(rs,cs)\n",
    "                # 更新行和\n",
    "                rs -= x\n",
    "                # 更新列和\n",
    "                colSum[j] -= x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        '''\n",
    "        result = []\n",
    "        m = len(rowSum)\n",
    "        n = len(colSum)\n",
    "        def buildList(i):\n",
    "            if(i == m):\n",
    "                return\n",
    "            ceils = []\n",
    "            for j in range(n):\n",
    "                num = min(rowSum[i], colSum[j])\n",
    "                ceils.append(num)\n",
    "                rowSum[i] -= num \n",
    "                colSum[j] -= num \n",
    "            result.append(ceils[:])\n",
    "            buildList(i+1)\n",
    "            return\n",
    "        buildList(0)\n",
    "        return result\n",
    "        '''\n",
    "        m = len(rowSum)\n",
    "        n = len(colSum)\n",
    "        result = []\n",
    "        for i in range(m):\n",
    "            ceils = []\n",
    "            for j in range(n):\n",
    "                num = min(rowSum[i], colSum[j])\n",
    "                ceils.append(num)\n",
    "                rowSum[i] -= num \n",
    "                colSum[j] -= num \n",
    "            result.append(ceils)\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m = len(rowSum)\n",
    "        n = len(colSum)\n",
    "        result = [[0]*n for _ in range(m)]\n",
    "        x=y=0\n",
    "        while x<m and y<n:\n",
    "            if rowSum[x]<=colSum[y]:\n",
    "                result[x][y]=rowSum[x]\n",
    "                colSum[y]=colSum[y]-rowSum[x]\n",
    "                x += 1\n",
    "            else:\n",
    "                result[x][y]=colSum[y]\n",
    "                rowSum[x]=rowSum[x]-colSum[y]\n",
    "                y+=1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        # 贪心\n",
    "        # r = len(rowSum)\n",
    "        # c = len(colSum)\n",
    "        # matrix = [[0]*c for _ in range(r)]\n",
    "\n",
    "        # for i, rs in enumerate(rowSum):\n",
    "        #     for j, cs in enumerate(colSum):\n",
    "        #         x = min(rs, cs)\n",
    "        #         matrix[i][j] = x \n",
    "        #         rs -= x \n",
    "        #         colSum[j] -= x\n",
    "        # return matrix\n",
    "\n",
    "\n",
    "        # 贪心\n",
    "        \"\"\"贪心算法，每次查找行和与列和的最小元素进行填充\"\"\"\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        result = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):                                  # 先行后列\n",
    "            for j in range(n):                              # 先左后右\n",
    "                result[i][j] = min(rowSum[i], colSum[j])    # 取值为行和与列和的最小值\n",
    "                rowSum[i] -= result[i][j]                   # 已填充元素，更新行和\n",
    "                colSum[j] -= result[i][j]                   # 更新列和\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\r\n",
    "        m, n = len(rowSum), len(colSum)\r\n",
    "        res = [[0] * n for _ in range(m)]\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                res[i][j] = min(rowSum[i], colSum[j])\r\n",
    "                rowSum[i] -= res[i][j]\r\n",
    "                colSum[j] -= res[i][j]\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "\n",
    "\n",
    "        rows = len(rowSum)\n",
    "        cols = len(colSum)\n",
    "        matrix = [[0] * cols for _ in range(rows)]\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                val = min(rowSum[i], colSum[j])\n",
    "                matrix[i][j] = val\n",
    "                rowSum[i] -= val\n",
    "                colSum[j] -= val\n",
    "\n",
    "        return matrix "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m = len(rowSum)\n",
    "        n = len(colSum)\n",
    "        matrix = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                matrix[i][j] = min(rowSum[i], colSum[j])\n",
    "                rowSum[i] -= matrix[i][j]\n",
    "                colSum[j] -= matrix[i][j]\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum, colSum):\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        matrix = [[0 for j in range(n)] for i in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                element = min(rowSum[i], colSum[j])\n",
    "                matrix[i][j] = element\n",
    "                rowSum[i] -= element\n",
    "                colSum[j] -= element\n",
    "\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        for i, rs in enumerate(rowSum):\n",
    "            for j, cs in enumerate(colSum):\n",
    "                mat[i][j] = x = min(rs, cs)\n",
    "                rs -= x\n",
    "                colSum[j] -= x\n",
    "        return mat\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m = len(rowSum)\n",
    "        n = len(colSum)\n",
    "        result = [[0]*n for _ in range(m)]\n",
    "        x=y=0\n",
    "        while x<m and y<n:\n",
    "            if rowSum[x]<=colSum[y]:\n",
    "                result[x][y]=rowSum[x]\n",
    "                colSum[y]=colSum[y]-rowSum[x]\n",
    "                x += 1\n",
    "            else:\n",
    "                result[x][y]=colSum[y]\n",
    "                rowSum[x]=rowSum[x]-colSum[y]\n",
    "                y+=1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m=len(rowSum)\n",
    "        n=len(colSum)\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if rowSum[i]==0:\n",
    "                    break\n",
    "                now=min(rowSum[i],colSum[j])\n",
    "                dp[i][j]=now\n",
    "                rowSum[i]-=now\n",
    "                colSum[j]-=now\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        n, m = len(rowSum), len(colSum)\n",
    "        g = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                g[i][j] = min(rowSum[i], colSum[j])\n",
    "                rowSum[i] -= g[i][j]\n",
    "                colSum[j] -= g[i][j]\n",
    "        return g\n",
    "'''\n",
    "    8 6 8\n",
    "5  [5,0,0]\n",
    "7  [3,4,0]\n",
    "10 [0,2,8]\n",
    "'''        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        rows_length = len(rowSum)\n",
    "        columns_length = len(colSum)\n",
    "        answer_list = [[0] * columns_length for _ in range(rows_length)]\n",
    "        for row in range(rows_length):\n",
    "            for column in range(columns_length):\n",
    "                answer_list[row][column] = min(rowSum[row], colSum[column])\n",
    "                rowSum[row] -= answer_list[row][column]\n",
    "                colSum[column] -= answer_list[row][column]\n",
    "        return answer_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        n = len(rowSum)\n",
    "        m = len(colSum)\n",
    "        row = [i for i in range(n)]\n",
    "        col = [i for i in range(m)]\n",
    "        row.sort(key = lambda x: rowSum[x])\n",
    "        col.sort(key = lambda x: colSum[x])\n",
    "        ans = [[0] * m for i in range(n)]\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < n:\n",
    "            minVal = min(rowSum[row[i]], colSum[col[j]])\n",
    "            ans[row[i]][col[j]] = minVal\n",
    "            rowSum[row[i]] -= minVal\n",
    "            if rowSum[row[i]] == 0:\n",
    "                i += 1\n",
    "            colSum[col[j]] -= minVal\n",
    "            if colSum[col[j]] == 0:\n",
    "                j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        ans = [[0] * len(colSum) for _ in range(len(rowSum))]\n",
    "        for i in range(len(rowSum)):\n",
    "            for j in range(len(colSum)):\n",
    "                temp_value = min(rowSum[i], colSum[j])\n",
    "                ans[i][j] = temp_value\n",
    "                rowSum[i] -= temp_value\n",
    "                colSum[j] -= temp_value\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m=len(rowSum)\n",
    "        n=len(colSum)\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                now=min(rowSum[i],colSum[j])\n",
    "                dp[i][j]=now\n",
    "                rowSum[i]-=now\n",
    "                colSum[j]-=now\n",
    "                if rowSum[i]==0:\n",
    "                    break\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        # 获取行数和列数\n",
    "        rows, cols = len(rowSum), len(colSum)\n",
    "        \n",
    "        # 初始化矩阵\n",
    "        matrix = [[0] * cols for _ in range(rows)]\n",
    "        \n",
    "        # 填充矩阵\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                # 选取当前行和列的和的最小值\n",
    "                matrix[i][j] = min(rowSum[i], colSum[j])\n",
    "                \n",
    "                # 更新剩余的行和列的和\n",
    "                rowSum[i] -= matrix[i][j]\n",
    "                colSum[j] -= matrix[i][j]\n",
    "        \n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        n, m = len(rowSum), len(colSum)\n",
    "        matrix = [[0] * m for _ in range(n)]\n",
    "        i = j = 0\n",
    "        while i < n and j < m:\n",
    "            v = min(rowSum[i], colSum[j])\n",
    "            matrix[i][j] = v\n",
    "            rowSum[i] -= v\n",
    "            colSum[j] -= v\n",
    "            if rowSum[i] == 0:\n",
    "                i += 1\n",
    "            if colSum[j] == 0:\n",
    "                j += 1\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m=len(rowSum)\n",
    "        n=len(colSum)\n",
    "        res=[[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[i][j]=min(colSum[j],rowSum[i])\n",
    "                colSum[j]-=res[i][j]\n",
    "                rowSum[i]-=res[i][j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        # m, n为矩阵的行（列）数\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        mat = [[0] * n for _ in range(m)]\n",
    "        k = 0\n",
    "        for i, rs in enumerate(rowSum):\n",
    "            for j, cs in enumerate(colSum):\n",
    "                k = min(rs, cs)\n",
    "                mat[i][j] = k\n",
    "                rs -= k\n",
    "                colSum[j] -= k\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        nr = len(rowSum)\n",
    "        nc = len(colSum)\n",
    "        ans = [[0 for _ in range(nc)] for _ in range(nr)]\n",
    "        for i in range(nr):\n",
    "            for j in range(nc):\n",
    "                ans[i][j] = min(rowSum[i], colSum[j])\n",
    "                rowSum[i] -= ans[i][j]\n",
    "                colSum[j] -= ans[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        n = len(rowSum)\n",
    "        m = len(colSum)\n",
    "        matrix = [[0] * m for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                matrix[i][j] = min(rowSum[i], colSum[j])\n",
    "                rowSum[i] -= matrix[i][j]\n",
    "                colSum[j] -= matrix[i][j]\n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m = len(rowSum)\n",
    "        n = len(colSum)\n",
    "\n",
    "        answer = [[0 for j in range(n)] for i in range(m)]\n",
    "        sumVal = sum(rowSum)\n",
    "        while sumVal > 0:\n",
    "            x, xv = self.getMinPositiveIndex(rowSum, m, sumVal+1)\n",
    "            y, yv = self.getMinPositiveIndex(colSum, n, sumVal+1)\n",
    "            v = min(xv, yv)\n",
    "            answer[x][y] = v\n",
    "            rowSum[x] -= v\n",
    "            colSum[y] -= v\n",
    "            sumVal -= v\n",
    "        return answer\n",
    "    \n",
    "\n",
    "    def getMinPositiveIndex(self, lst, n, maxValue):\n",
    "        p = 0\n",
    "        v = maxValue\n",
    "        for i in range(n):\n",
    "            if lst[i] > 0 and lst[i] < v:\n",
    "                v = lst[i]\n",
    "                p = i\n",
    "        return p, v\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum, colSum):\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        matrix = [[0 for j in range(n)] for i in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                element = min(rowSum[i], colSum[j])\n",
    "                matrix[i][j] = element\n",
    "                rowSum[i] -= element\n",
    "                colSum[j] -= element\n",
    "\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "\n",
    "        i = j = 0\n",
    "        while i < m and j < n:\n",
    "            if rowSum[i] < colSum[j]:\n",
    "                ans[i][j] = rowSum[i]\n",
    "                colSum[j] -= rowSum[i]\n",
    "                i += 1\n",
    "            elif rowSum[i] > colSum[j]:\n",
    "                ans[i][j] = colSum[j]\n",
    "                rowSum[i] -= colSum[j]\n",
    "                j += 1\n",
    "            else:\n",
    "                ans[i][j] = rowSum[i]\n",
    "                i += 1\n",
    "                j += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        n,m=len(rowSum),len(colSum)\n",
    "        lst1=[[rowSum[i],i] for i in range(n)]\n",
    "        lst2=[[colSum[i],i] for i in range(m)]\n",
    "        lst1.sort()\n",
    "        lst2.sort()\n",
    "        matrix=[[0]*m for i in range(n)]\n",
    "        while lst1:\n",
    "            a=lst1[0]\n",
    "            b=lst2[0]\n",
    "            #[a[1],b[1]]\n",
    "            if a[0]<=b[0]:\n",
    "                lst1.pop(0)\n",
    "                lst2[0][0]-=a[0]\n",
    "                matrix[a[1]][b[1]]=a[0]\n",
    "            else:\n",
    "                lst2.pop(0)\n",
    "                lst1[0][0]-=b[0]\n",
    "                matrix[a[1]][b[1]]=b[0]\n",
    "        return matrix\n",
    "                \n",
    "            \n",
    "                \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        r,c = len(rowSum),len(colSum)\n",
    "        sum_r = [0 for i in range(r)]\n",
    "        sum_c = [0 for i in range(c)]\n",
    "        res = []\n",
    "        for i in range(r):\n",
    "            tmp = []\n",
    "            for j in range(c):\n",
    "                t = min(rowSum[i]-sum_r[i],colSum[j]-sum_c[j])\n",
    "                tmp.append(t)\n",
    "                sum_r[i] += t\n",
    "                sum_c[j] += t\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:\n",
    "        lenRow = len(rowSum)\n",
    "        lenCol = len(colSum)\n",
    "        ans = [[0 for i in range(lenCol)] for j in range(lenRow)]\n",
    "\n",
    "        for i in range(lenRow):\n",
    "            for j in range(lenCol):\n",
    "                tmp = min(rowSum[i], colSum[j])\n",
    "                ans[i][j] = tmp\n",
    "                rowSum[i] = rowSum[i] - tmp\n",
    "                colSum[j] = colSum[j] - tmp\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreMatrix(self, rowSum, colSum):\n",
    "        m, n = len(rowSum), len(colSum)\n",
    "        matrix = [[0 for j in range(n)] for i in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                element = min(rowSum[i], colSum[j])\n",
    "                matrix[i][j] = element\n",
    "                rowSum[i] -= element\n",
    "                colSum[j] -= element\n",
    "\n",
    "        return matrix"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
